package com.kk.datastructure.tree.foundactiontree;
//package com.kk.datastructure.tree;
//
//
///**
// * title: 前中后序查找
// * @author 阿K
// * 2020年12月30日 下午11:49:44 
// */
//public class BinaryTreeDemo2 {
//
//	public static void main(String[] args) {
//
//		// 创建二叉树
//		BinaryTree binaryTree = new BinaryTree();
//
//		// 创建需要的结点
//		HeroNode root = new HeroNode(1, "宋江");
//		HeroNode node2 = new HeroNode(2, "吴用");
//		HeroNode node3 = new HeroNode(3, "卢俊义");
//		HeroNode node4 = new HeroNode(4, "林冲");
//		HeroNode node5 = new HeroNode(5, "关胜");
//
//		// 加入树
//		root.setLeft(node2);
//		root.setRight(node3);
//		node3.setRight(node4);
//		node3.setLeft(node5);
//		binaryTree.setRoot(root);
//
//		System.out.println("前序遍历，预计统计次数：4 ===> 查找顺序 1，2，3，5，4");
//		binaryTree.perOrderSearch(5);
//
//		System.out.println("中序遍历，预计统计次数：3 ===》 查找顺序 2，1，5，3，4");
//		binaryTree.infixOrderSearch(5);
////
//		System.out.println("后序遍历，预计统计次数：2 ===》 查找顺序 2,5, 4,3,1");
//		binaryTree.postOrderSearch(5);
//	}
//}
//
//// 定义二叉树 
//class BinaryTree {
//
//	private HeroNode root;// 根节点
//
//	public void setRoot(HeroNode root) {
//		this.root = root;
//	}
//
//	// 前序遍历查找
//	public HeroNode perOrderSearch(int no) {
//		if (root != null) {
//			return root.perOrderSearch(no);
//		} else {
//			return null;
//		}
//	}
//
//	// 中序遍历查找
//	public HeroNode infixOrderSearch(int no) {
//		if (root != null) {
//			return root.infixOrderSearch(no);
//		} else {
//			return null;
//		}
//	}
//
//	// 后序遍历查找
//	public HeroNode postOrderSearch(int no) {
//		if (root != null) {
//			return root.postOrderSearch(no);
//		} else {
//			return null;
//		}
//	}
//}
//
//// 定义节点
//class HeroNode {
//	private int no;
//	private String name;
//	private HeroNode left; // 左节点（默认为null）
//	private HeroNode right; // 右节点（默认为null）
//
//	public HeroNode(int no, String name) {
//		this.no = no;
//		this.name = name;
//	}
//
//	/**
//	 * 须知：关于查找次数的统计
//	 * 为了有效的统计出正确的次数，应该放在 if(this.no == no) 上面
//	 * @param no
//	 * @return
//	 */
//
//	// 节点的前序遍历查找
//	public HeroNode perOrderSearch(int no) {
//		System.out.println("记录前序遍历查找，打印次数决定查找运行次数！");
//		// 比较当前节点是否
//		if (this.no == no) {
//			return this;
//		}
//		// 1、判断当前节点的左子节点是否为空，若不为空，则左递归前序查找
//		// 2、若左递归前序查找，找到节点则返回
//		HeroNode resNode = null;
//		if (this.left != null) {
//			resNode = this.left.perOrderSearch(no);
//		}
//		if (resNode != null) {// 说明在左子树上找到了
//			return resNode;
//		}
//		// 1、当前节点的右子树是否为空，若不为空，则右递归前序查找
//		// 2、若右递归前序查找，找到节点则返回
//		if (this.right != null) {
//			resNode = this.right.perOrderSearch(no);
//		}
//		return resNode;
//	}
//
//	// 节点的中序遍历查找
//	public HeroNode infixOrderSearch(int no) {
//		// 1、判断当前左节点是否为空，若不为空，则继续左递归中序遍历查找
//		HeroNode resNode = null;
//		if (this.left != null) {
//			resNode = this.left.infixOrderSearch(no);
//		}
//		// 2、若不为空，则返回（既找到）
//		if (resNode != null) {
//			return resNode;
//		}
//		System.out.println("进入中序查找的次数统计");
//		// 3、和当前节点进行比较，若是则返回
//		if (this.no == no) {
//			return this;
//		}
//		// 4、若不是，则继续右递归中序遍历查找
//		if (this.right != null) {
//			resNode = this.right.infixOrderSearch(no);
//		}
//		return resNode;
//	}
//
//	// 节点的后序遍历查找
//	public HeroNode postOrderSearch(int no) {
//		// 1、判断当前左节点是否为空，若不为空，则继续左递归后序遍历查找
//		HeroNode resNode =null;
//		if(this.left!=null) {
//			resNode = this.left.postOrderSearch(no);
//		}
//		// 2、若不为空，则返回
//		if(resNode !=null) {
//			return resNode;
//		}
//		// 3、若当前左子树没有找到，则开始右子树后序递归遍历查找
//		if(this.right!=null) {
//			resNode = this.right.postOrderSearch(no);
//		}
//		// 4、若不为空，则返回
//		if(resNode!=null) {
//			return resNode;
//		}
//		System.out.println("进入后序号查找次数统计");
//		// 5、若左右子树都没有找到，就比较当前节点是否
//		if(this.no==no) {
//			return this;
//		}
//		return resNode;
//	}
//
//	public int getNo() {
//		return no;
//	}
//
//	public void setNo(int no) {
//		this.no = no;
//	}
//
//	public String getName() {
//		return name;
//	}
//
//	public void setName(String name) {
//		this.name = name;
//	}
//
//	public HeroNode getLeft() {
//		return left;
//	}
//
//	public void setLeft(HeroNode left) {
//		this.left = left;
//	}
//
//	public HeroNode getRight() {
//		return right;
//	}
//
//	public void setRight(HeroNode right) {
//		this.right = right;
//	}
//
//	@Override
//	public String toString() {
//		return "HeroNode [no=" + no + ", name=" + name + "]";
//	}
//}
